Subject: Re: Public implementation of Lists/Nodes?
From: [email-masked] (Neil Gall)
Date: Wed, 2 Feb 1994 13:30:03 GMT
Newsgroups: comp.sys.amiga.programmer

Cedric Beust ([email-masked]) wrote:

:       I was wondering if someone had re-written the functions
:       NewList(), AddTail(), etc... in order to be able to use them in
:       a non-Amiga environment? I really like them and
:       would like to use the same API in my work (and avoid
:       implementing them personally of course :-)).

I implemented Exec-style lists in C++ for a project I was working on
about three months ago.  They're really easy to implement once you
work out what's going on.  Here's a solution in C:

You need to define the structures:

struct List
{
    struct Node *Head;
    struct Node *Tail;
    struct Node *TailPred;
};

struct Node
{
    struct Node *Succ;
    struct Node *Pred;
};

And the following functions:

void NewList(struct List *list)
{
    list->Head = (struct Node *)&list->Tail;
    list->Tail = NULL;
    list->TailPred = (struct Node *)list;
}

void AddHead(struct List *list,struct Node *node)
{
    node->Succ=list->Head;
    node->Pred=(struct Node *)list;
    list->Head->Pred=node;
    list->Head=node;
}

void AddTail(struct List *list,struct Node *node)
{
    node->Succ=(struct Node *)&list->Tail;
    node->Pred=list->TailPred;
    list->TailPred->Succ=node;
    list->TailPred=node;
}

struct Node *RemHead(struct List *list)
{
    struct Node *node=NULL;

    if (list->Head->Succ)
    {	
    	node=list->Head;
    
	list->Head->Succ->Pred=(struct Node *)list;
	list->Head=list->Head->Succ;
    }
    
    return node;
}

struct Node *RemTail(struct List *list)
{
    struct Node *node=NULL;
    
    if (list->TailPred->Pred)
    {
    	node=list->TailPred;
    
    	list->TailPred->Pred->Succ=list->TailPred;
    	list->TailPred=list->TailPred->Pred;
    }
    
    return node;
}

void Remove(struct Node *node)
{
    node->Succ->Pred=node->Pred;
    node->Pred->Succ=node->Succ;
}

That's all I can remember at the moment.  AddHead() can be generalised
to get Insert(list,node,pred), and Enqueue() is done simply by scanning
the list for a node with the right priority (you have to include a
priority field into the node structure).

In C++, these were really good.  List and Node were classes, and everything
which was "listable" was derived from Node, inheriting all the Node methods.
If I remember correctly, most of the operations were List methods, so say
you had a list called foo, and wanted to add a node bar, you did

	foo.AddTail(bar);
	
Then I overloaded << to mean AddTail(), so you could say

	foo << bar;
	
Of course this returned foo, so you could say

	foo << bar << baz << boz;
	
to add a number of objects to the tail of the list.  Similarly you
could use >> to mean RemHead, thus implementing a queue with
operators.

--
Neil Gall				Queensferry Telecoms Operation
[email-masked]		Hewlett-Packard Ltd.
031-331-7895				South Queensferry, Scotland